﻿#pragma once
#include<iostream>
using namespace std;
template<class K,class V>
struct AVLNode {
	pair<K, V> _kv;
	AVLNode<K, V> _parent;
	AVLNode<K, V> _left;
	AVLNode<K, V> _right;
	int _bf;

	AVLNode(const pair<K, V> kv)
		:_kv(kv)
		,_parent(nullptr)
		,_left(nullptr)
		,right(nullptr)
		,_bf(0)
	{}
};
template<class K,class V>
class AVL {
	typedef AVLNode* Node;

	void insert(const pair<K, V> kv) {
		Node newnode = new Node(kv);
		if (_root == nullptr) {
			_root = newnode;
		}
		
			Node cur = _root;
			Node parent = nullptr;
			while (cur) {
				if (cur->_kv.first< kv.first) {
					parent = cur;
					cur = cur->_right;
				}
				else {
					parent = cur;
					cur = cur->_left;
				}
			}
			cur = newnode;
			if (parent->_kv.first<kv.first) {
				parent->right = newnode;
			}
			else {
				parent->_left = newnode;
			}
			// 链接父亲
			cur->_parent = parent;

			// 控制平衡
			// 更新平衡因子
			while (parent)
			{
				if (cur == parent->_left)
					parent->_bf--;
				else
					parent->_bf++;

				if (parent->_bf == 0)
				{
					break;
				}
				else if (parent->_bf == 1 || parent->_bf == -1)
				{
					cur = parent;
					parent = parent->_parent;
				}
				else if (parent->_bf == 2 || parent->_bf == -2)
				{
					// 旋转

					break;
				}
				else
				{
					assert(false);
				}
			}
			return true;
	}
	void RotateR(Node parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		// 需要注意除了要修改孩⼦指针指向，还是修改⽗亲 
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		Node* parentParent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		// parent有可能是整棵树的根，也可能是局部的⼦树 
		// 如果是整棵树的根，要修改_root 
		// 如果是局部的指针要跟上⼀层链接 
		if (parentParent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
			 {
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
		parent->_bf = subL->_bf = 0;
	}
	void RotateL(Node parent)
	{
		Node subR = parent->_right;
		Node subRL = subR->_left;
		parent->_right = subRL;
		if (subRL) subRL->_parent = parent;
		Node pParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (pParent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (pParent->_left == parent)
			{
				pParent->_left = subR;
			}
			else
			{
				pParent->_right = subR;
			}
		}
		subR->_bf = 0; parent->_bf = 0;
	}
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);
		if (bf == 0)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subL->_bf = -1;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		RotateR(parent->_right);
		RotateL(parent);
		if (bf == 0)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	private:
		bool _IsAVLTree(Node* pRoot)
		{
			if (nullptr == pRoot)
				return true;

			int leftHeight = _Height(pRoot->_pLeft);
			int rightHeight = _Height(pRoot->_pRight);

			if (abs(rightHeight - leftHeight) > 1 ||
				rightHeight - leftHeight != pRoot->_bf)
				return false;

			return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
		}

private:

	Node _root=nullptr;
};
